package com.c2b.algorithm.newcoder.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <a href="https://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">二叉树的后序遍历</a>
 * <p>给定一个二叉树，返回他的后序遍历的序列。</p>
 * <p>后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。</p>
 * <p>数据范围：二叉树的节点数量满足1≤n≤100  ，二叉树节点的值满足1≤val≤100  ，树的各节点的值各不相同</p>
 *
 * @author c2b
 * @since 2023/3/13 16:04
 */
public class BM0025PostorderTraversal_S {

    public int[] postorderTraversal (TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        List<Integer> resList = new ArrayList<>();
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            resList.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right!=null)
                stack.push(node.right);
        }
        int[] resArray = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            resArray[i] = resList.get(resList.size() - 1 - i);
        }
        return resArray;
    }

    public int[] postorderTraversal2 (TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> resList = new ArrayList<>();
        recursion(resList, root);
        int[] resArray = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            resArray[i] = resList.get(i);
        }
        return resArray;
    }

    private void recursion(List<Integer> resList, TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        // 左
        recursion(resList, treeNode.left);
        // 右
        recursion(resList, treeNode.right);
        // 根
        resList.add(treeNode.val);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        BM0025PostorderTraversal_S bm0025PostorderTraversal_s = new BM0025PostorderTraversal_S();
        for (int i : bm0025PostorderTraversal_s.postorderTraversal(root)) {
            System.out.println(i);
        }
    }
}
